package 栈队列与哈希表;

import java.util.Stack;

/**
 * 输入两个整数序列，其中一个序列表示栈的push（入）顺序，判断另一个序列有没有可能是对应的pop（出）顺序。
 * 分析与解答：假如输入的push 序列是1、2、3、4、5，那么3、2、5、4、1 就有可能是一个pop 序列，但5、3、4、1、2 就不可能是它的一个pop 序列。
 * 主要思路：使用一个栈来模拟入栈顺序，具体步骤如下：
 * 1）把push序列依次入栈，直到栈顶元素等于pop序列的第一个元素，然后栈顶元素出栈，pop序列移动到第二个元素。
 * 2）如果栈顶继续等于pop序列现在的元素，则继续出栈并pop后移；否则对push序列继续入栈。
 * 3）如果push序列已经全部入栈，但是pop序列未全部遍历，而且栈顶元素不等于当前pop元素，那么这个序列不是一个可能的出栈序列。
 * 如果栈为空，而且pop序列也全部被遍历过，则说明这是一个可能的pop序列。下图给出一个合理的pop序
 */
public class D如何根据入栈序列判断可能的出栈序列 {
    public static boolean isPopSerial(String push, String pop) {
        if (push == null || pop == null) {
            return false;
        }
        int pushLen = push.length();
        int popLen = pop.length();
        if (pushLen != popLen) {
            return false;
        }
        int pushIndex = 0;
        int popIndex = 0;
        Stack<Character> stack = new Stack<Character>();
        while (pushIndex < pushLen) {
            //把push序列依次入栈，直到栈顶元素等于pop序列的第一个元素
            stack.push(push.charAt(pushIndex));
            pushIndex++;
            //栈顶元素出栈，pop序列移动到下一个元素
            while (!stack.empty() && stack.peek() == pop.charAt(popIndex)) {
                stack.pop();
                popIndex++;
            }
        }
        //栈为空，且pop序列中元素都被遍历过
        return stack.empty() && popIndex == popLen;
    }

    public static void main(String[] args) {
        String push = "12345";
        String pop = "32541";
        if (isPopSerial(push, pop)) {
            System.out.println(true);
        } else {
            System.out.println(false);
        }

        System.out.println(hexStr2Str("E5A4A7E78CAB"));
    }

    /**
     *  * 16进制直接转换成为字符串(无需Unicode解码)
     *  * @param hexStr  Byte字符串(Byte之间无分隔符
     *
     * @author xxs
     *  * @return 对应的字符串
     *  
     */
    public static String hexStr2Str(String hexStr) {
        String str = "0123456789ABCDEF"; //16进制能用到的所有字符 0-15
        char[] hexs = hexStr.toCharArray();//toCharArray() 方法将字符串转换为字符数组。
        int length = (hexStr.length() / 2);//1个byte数值 -> 两个16进制字符
        byte[] bytes = new byte[length];
        int n;
        for (int i = 0; i < bytes.length; i++) {
            int position = i * 2;//两个16进制字符 -> 1个byte数值
            n = str.indexOf(hexs[position]) * 16;
            n += str.indexOf(hexs[position + 1]);
            // 保持二进制补码的一致性 因为byte类型字符是8bit的  而int为32bit 会自动补齐高位1  所以与上0xFF之后可以保持高位一致性
            //当byte要转化为int的时候，高的24位必然会补1，这样，其二进制补码其实已经不一致了，&0xff可以将高的24位置为0，低8位保持原样，这样做的目的就是为了保证二进制数据的一致性。
            bytes[i] = (byte) (n & 0xff);
        }
        return new String(bytes);
    }

    /**
     *  * 字符串转换成为16进制(无需Unicode编码)
     *  * @param str 待转换的ASCII字符串
     *
     * @author xxs
     *  * @return byte字符串 （每个Byte之间空格分隔）
     *  
     */
    public static String str2HexStr(String str) {
        char[] chars = "0123456789ABCDEF".toCharArray();//toCharArray() 方法将字符串转换为字符数组。
        StringBuilder sb = new StringBuilder(""); //StringBuilder是一个类，可以用来处理字符串,sb.append()字符串相加效率高
        byte[] bs = str.getBytes();//String的getBytes()方法是得到一个操作系统默认的编码格式的字节数组
        int bit;
        for (int i = 0; i < bs.length; i++) {
            bit = (bs[i] & 0x0f0) >> 4; // 高4位, 与操作 1111 0000
            sb.append(chars[bit]);
            bit = bs[i] & 0x0f;  // 低四位, 与操作 0000 1111
            sb.append(chars[bit]);
            sb.append(' ');//每个Byte之间空格分隔
        }
        return sb.toString().trim();
    }
}
